

/**
 * 
 * RBTree
 * 
 * An implementation of a Red Black Tree with
 * non-negative, distinct integer values
 * 
 * Submitted by:
 * Name			Username	ID Number
 * Noam Mor		noammor		300094836
 * Hila Peleg	hilapel1	200167591
 * 
 */

public class RBTree {
	/**
	 * The root node of the tree. Set to the nil sentinel when the tree is empty.
	 */
	public RBNode root = nil;
	/**
	 * The size of the tree, needed for a List-less implementation of toIntArray()
	 */
	private int size = 0;
	
	/**
	 * Denotes the color of each RBNode in the RBTree.
	 */
	private enum Color {
		red,
		black
	}
	

	
  /**
   * Returns true if and only if the tree is empty<br>
   * 
   * <u>Complexity:</u> The function performs one constant command - O(1)
   *  
   * preconditions: none
   * postcondition: return true iff contains(i)==false for all i
   * 
   * @return True if the tree has no nodes in it.
   */
  public boolean empty() {
    return root == nil;
  }

  /**
   * Returns true if and only if the tree contains i<br>
   * 
   * The function runs <code>find</code> to search for the node containing 
   * i. Since find may return an insertion point and not the value itself,
   * the key is checked to match. <br>
   * 
   * <u>Complexity:</u> The function uses <code>find</code> which runs at 
   * O(log(n)), and does a constant amount of work otherwise, so the total
   * complexity is O(log(n)).
   *  
   * preconditions: none
   * postcondition: returns true iff i is in the tree
   * 
   * @param i The non-negative integer to be looked up in the tree.
   * @return True if the tree contains i and false otherwise. 
   */
  public boolean contains(int i)
  {
	   RBNode find_result = find(i);
	   if (find_result == nil) {
		   return false;
	   }
	   
	   return find_result.value == i;
  }
  
  /** 
   * inserts the integer i into the binary tree; the tree
   * must remain valid (keep its invariants).<br>
   * 
   * The function begins much like the normal binary-tree insert, by finding
   * the insertion point. A red node is inserted (except for a black root) as
   * the correct child of the insertion point, and <code>insertFixup</code> is
   * called to preserve the Red-Black invariants.<br>
   * <u>Complexity:</u> the function uses both <code>find</code> which runs
   * at O(log(n)) and <code>insertFixup</code> which runs at O(log(n)) for a
   * total complexity of O(log(n)).
   * 
   * precondition:  contains(i) == false (that is, i is not in the list )
   * postcondition: contains(i) == true (that is, i is in the list)
   * 
   * @param i The non-negative value to insert into the tree
   */
   public void insert(int i) {
	  RBNode insertionPoint = find(i);
	  //insertionPoint is either null or a point of insertion for i, not i itself
	  
	  //First special case: have to add a root
	  if (insertionPoint == nil) {
		  root = new RBNode(i, nil, Color.black);
		  size = 1;
		  return;
	  }
	  
	  RBNode newNode = new RBNode(i, insertionPoint, Color.red);
	  if (insertionPoint.value < i) {
		  insertionPoint.right = newNode;
	  }
	  else {
		  insertionPoint.left = newNode;
	  }
	  
	  insertFixup(newNode);
	  ++size;
	  
   }
   
   /** 
    * deletes the integer i from the binary tree; the tree
    * must remain valid (keep its invariants).<br>
    * 
    * The function is very similar to the delete function of a simple binary search tree.<br>
    * First, the node that contains the key that is to be deleted is located.
    * Then, the node that is to be removed from the tree is located.
    * Lastly, the node to be removed is removed and its value is copied to the node that contained
    * the deleted key. <br>
    * If the deleted node was black, the function deleteFixup() is called.<br>
    * 
    * <u>Complexity</u>:
    * The most costly operations are find(), which is O(log n), and successor, also O(log n).
    * other than that, the function performs a fixed number of O(1) operations,
    * and a call to deleteFixup which is O(log n) as well.
    * 
    * Total: O(log n)<br>
    * 
    * precondition:  contains(i) == true (that is, i is not in the list )
    * postcondition: contains(i) == false (that is, i is in the list)
    */
    public void delete(int i)
    {
 	   size--;
 	   RBNode toDelete = find(i); //precondition promises it's there
 	   //if it's a red leaf, rip it out
 	   if ((toDelete.left == nil) &&(toDelete.right == nil) && toDelete.color ==Color.red) {
 		   if (toDelete.parent == nil) { // root
 			   root = nil;
 		   }
 		   if (toDelete.parent.right == toDelete) {
 			   toDelete.parent.right = nil;
 		   }
 		   else {//left
 			   toDelete.parent.left = nil;
 		   }
 	   }
 	   else //one or more children
 	   {
 		   RBNode deletionPoint = nil;
 		   if ((toDelete.left == nil) || (toDelete.right == nil)){ //one child
 			   deletionPoint = toDelete;
 		   }
 		   else{ //two children
 			   deletionPoint = successor(toDelete);
 		   }
 		   RBNode x = nil;
 		   if (deletionPoint.left != nil) {
 			   x = deletionPoint.left;
 		   } else {
 			   x = deletionPoint.right;
 		   }
 		   
 		   x.parent = deletionPoint.parent;
 		   
 		   if (deletionPoint.parent == nil ) {//deleting the root
 			   root = x;
 		   }
 		   else if (deletionPoint == deletionPoint.parent.left) {
 			   deletionPoint.parent.left = x;
 		   }
 		   else
 		   {
 			   deletionPoint.parent.right = x;
 		   }
 		   if (toDelete != deletionPoint)
 		   {
 			   toDelete.value = deletionPoint.value;
 		   }
 		   if (deletionPoint.color == Color.black)
 		   {
 			   deleteFixup(x);
 		   }
 	   }
    }   
    
    
    /**
     * Returns the smallest key in the tree. If the tree
     * is empty, returns -1;<br>
     * 
     * Calls the private overload <code>min(RBNode)</code> with the 
     * root of the tree as its parameter. Like <code>min(RBNode)</code> to
     * which the work is delegated, complexity is O(logn)<br>
     * 
     * precondition: none
     * postcondition: none
     */
    public int min()
    {
 	   RBNode min_node = min(root);
 	   if (min_node == nil) {
 		   return -1;
 	   }
 	   return min_node.value;
    }
    
    /** 
     * Returns the largest key in the tree. If the tree
     * is empty, returns -1;<br>
     * 
     * Function starts from the root and seeks the right-most node 
     * in the tree.<br>
     * 
     * <u>Complexity:</u> Travels the height of the tree, at O(h) = O(logn)
     * 
     * precondition: none
     * postcondition: none
     */
    public int max()
    {
 	   if (empty()) {
 		   return -1;
 	   }
 	   
 	   RBNode i = root;
 	   
 	   while (i.right != nil) {
 		   i = i.right;
 	   }
 	   
 	   return i.value;
    }
    
    /**
     * Returns true iff the tree is a complete binary tree.
     * 
     * Implemented by a call to <code>isComplete_helper(root)</code>, which
     * visits each tree node once, for running time of \Theta(n).
     * 
     * preconditions: none
     * postconditions: none
     */
	public boolean isComplete()
	{
		if (empty())
			return true;
		return isComplete_helper(root) != -1;
	}    
	
  /**  
   * Returns an int[] array containing the values stored in the tree,
   * in ascending order.
   * 
   * Uses <code>inOrder</code> which traverses the tree at \Theta(n), to
   * fill the output array.
   * 
   * preconditions: none
   * postconditions: returns an array containing exactly the tree's elements in
   *                 ascending order.
   */
  public int[] toIntArray()
  {
	 if (empty()) {
		 return new int[0];
	 }
	 
	 int[] arr = new int[size];
	 inOrder(root,arr,0);
	 
	 return arr;
  }
    
  
  /**
   * Seeks the value i by normal binary search-tree "find":<br>
   * Smaller value is left of current node, larger value is right.<br>
   * <u>Complexity:</u> The implementation is iterative, and at WC will travel the height of the tree, 
   * O(h), where in a Red-Black tree h=log_2(n)<br>
   * Therefore this implementation is at O(log(n)). 
   * @param i The non-negative integer to find in the tree
   * @return Either the RBNode containing the value i, or the insertion point (successor or predecessor) for the value i. 
   */
  private RBNode find(int i) {
	   if (empty()) {
		   return nil;
	   }
	   
	  RBNode node = root;

	  RBNode prev = nil; // prev tracks one behind node.
	  
	  while (node != nil) {
		  if (node.value == i) {
			  return node;
		  }
		  prev = node;
		  if (node.value < i) {
			  node = node.right;
		  }
		  
		  // node.value > i
		  else {
			  node = node.left;
		  }
	  }
	  return prev;
  }
   
   /**
   * Performs a rotate-left of the arc between the nodes x and x.right.
   * @param x The parent node of the rotating arc. Precondition: x.right != null 
   */
   private void leftRotate(RBNode x) {
	   RBNode y = x.right;
	   x.right = y.left;
	   if (y.left != nil) {
		   y.left.parent = x;
	   }
	   y.parent = x.parent;
	   if (x.parent == nil) {
		   root = y;
	   }
	   else if (x == x.parent.left) {
		   x.parent.left = y;
	   }
	   else {
		   x.parent.right = y;
	   }
	   y.left = x;
	   x.parent = y;
   }
   
   /**
    * Performs a rotate-right of the arc between the nodes x and x.left.
    * @param x The parent node of the rotating arc. Precondition: x.left != null 
    */
   private void rightRotate(RBNode x) {
	   RBNode y = x.left;
	   x.left = y.right;
	   if (y.right != nil) {
		   y.right.parent = x;
	   }
	   y.parent = x.parent;
	   if (x.parent == nil) {
		   root = y;
	   }
	   else if (x == x.parent.right) {
		   x.parent.right = y;
	   }
	   else {
		   x.parent.left = y;
	   }
	   y.right = x;
	   x.parent = y;
   }
 
   /**
    * This is where the main logic for performing the insert resides. 
    * It handles the five basic cases of insertion-fixup, three as defined in CLRS 
    * for cases where me is red and me.parent is red, and the other two basic cases: <br>
    * <ol><li>me is the root. Color it black to preserve R-B invariant.</li>
    * <li>me.parent is the root, need only to call fixup on the root to make sure it is okay.</li>
    * <li>Case I: me has a red parent and a red uncle - color flip is performed and
    *  insertFixup(grandparent) called.</li>
    * <li>Case II: me has a red parent and a black uncle. The (me,parent) edge is 
    * an inner vertex. Rotate the (me,parent) edge to turn it into an outer vertex 
    * and turn the problem into Case III.</li>
    * <li>Case III: implemented by <code>doCase3</code> method</li></ol><br>
    * <u>Complexity:</u> In the worst case, Case I will carry up the tree, O(h) times, or O(log(n)) 
    * @param me The node to begin the fixup at.
    */
   private void insertFixup(RBNode me) {
	   if (me.parent == nil) { //me is the root
		   me.color = Color.black; //The root is black.
		   //That's it.
		   return;
	   }
	   
	   RBNode parent = me.parent;
	   //It doesn't matter what I am, if my parent is black, I'm done.
	   if (parent.color == Color.black) {  
		   return;
	   }
	   
	   //I have a parent, my parent is red. 
	   //Now what?
	   
	   if (parent.parent == nil) { //red parent + no grandparent
		   //means parent is the root and it's red.
		   //Call fixup to fix it, and you're done.
		   insertFixup(parent);
		   return;
	   }
	   RBNode uncle = getSibling(parent);
	   RBNode grandparent = parent.parent;
	   
	   if ((uncle != nil) && (uncle.color == Color.red)) {
		   //there's a grandfather (we know so, we got uncle)
		   //and it's black. So Case I:
		   
		   //do color flip:
		   parent.color = Color.black;
		   uncle.color = Color.black;
		   grandparent.color = Color.red;
		   //Now problem has shifted up to grandparent
		   insertFixup(grandparent);
		   return;
		   
	   }
	   else {//uncle is black or nonexistent, Case II or III
		   if ((me == parent.right) && (parent == grandparent.left)) {
				leftRotate(parent);
				doCase3(me.left);
			} else if ((me == parent.left) && (parent == grandparent.right)) {
				rightRotate(parent);
				doCase3(me.right);
			}
			else {
				//Outer vertex, Case III, terminal case
				doCase3(me);

			}

	   }
	   
   }
   /**
    * Performs Case III of insertFixup, which is the terminal case.<br>
    * me is a red node, as is parent, and the (me,parent) edge is an 
    * outer vertex. Flip the colors on parent and grandparent, and 
    * rotate to make parent the root of the subtree instead of grandparent 
    * @param me The node from which to perform fixup Case III. Precondition: me.parent.parent != nil
    */
	private void doCase3(RBNode me) {
		RBNode parent = me.parent; 
		RBNode grandparent = parent.parent;
		parent.color = Color.black;
		grandparent.color = Color.red;
	   
		if ((me == parent.left) && (parent == grandparent.left)) {
		   rightRotate(grandparent);
		}
		else {
		   leftRotate(grandparent);
		}
	}

	/**
	 * Returns me's sibling or nil if none exists
	 * precondition: me.parent != null 
	 */
   private RBNode getSibling(RBNode me) {
	   RBNode right = me.parent.right;
	   RBNode left = me.parent.left;
	   
	   if (me == right) {
		   return left;
	   }
	   else { //me == left
		   return right;
	   }
		   
   }
   
   /**
    * Performs the fixup to maintain RB invariants after delete.<br>
    * Getting to deleteFixup means that the path from node x to the root is lacking one black.
    * Now, the function regrads four cases:<br>
    * 
    * <ol><li> If x's sibling is red, then since it must have black children, it is possible to switch
    * the colors of w and x.parent and then perform a left-rotation on x.parent. This leads to one
    * of the cases 2, 3 or 4.</li>
    * 
    * <li>If x's sibling's children are black, then since w is also black, we change w's color
    * (to red), and re-run the function on x.parent. (in the while loop)</li>
    * 
    * <li>If w is black, w.left is red and w.right is black, we switch the colors of w.left and
    * w, and then perform a right-rotation on w. In that case, the next iteration of the while loop
    * will enter case 4.</li>
    * 
    *  <li>If w is black and w.right is red, we can stop restore red-black status by simply switching
    *  the color of w.parent  and of w.right and then performing a leftRotate on x.parent.</li></ol>
    *  
    *  
    *  In the end of the function, x's color is set to black.
    * <u>Complexity:</u>
    * In cases 1, 3 and 4, the function exits after a fixed number of O(1) operations.
    * The worst case is when the function called in a case 2 situation, because that is the only
    * case when the loop is executed again. The loop can only be executed until x == root, and
    * since in each iteration of the loop x rises one level in the tree (gets one step closer
    * to it), the loop can be executed at most h(tree) times, which is of order O(log n).<br>
    * 
    * Total complexity: O(log n)
    * @param x The node from which to begin the fixup.
    */
   private void deleteFixup(RBNode x) {
	   while ((x != root) && (x.color == Color.black) ) {
		   if (x == x.parent.left) {
			   RBNode w = x.parent.right;
			   if (w.color == Color.red) { // Case 1
				   w.color = Color.black;
				   x.parent.color = Color.red;
				   leftRotate(x.parent);
				   w = x.parent.right;
			   }
			   
			  if (w.left.color == Color.black && w.right.color == Color.black) { // Case 2
				  w.color = Color.red;
				  x = x.parent;
			  } else if (w.right.color == Color.black) {
				  w.left.color = Color.black;					// Case 3
				  w.color = Color.red;
				  rightRotate(w);
				  w = x.parent.right;
			  } else {
				  w.color = x.parent.color;				// Case 4
				  x.parent.color = Color.black;
				  w.right.color = Color.black;
				  leftRotate(x.parent);
				  break;
			  }
		   } else {
			   RBNode w = x.parent.left;
			   if (w.color == Color.red) { // Case 1
				   w.color = Color.black;
				   x.parent.color = Color.red;
				   rightRotate(x.parent);
				   w = x.parent.left;
			   }
			   
			  if (w.right.color == Color.black && w.left.color == Color.black) { // Case 2
				  w.color = Color.red;
				  x = x.parent;
			  } else if (w.left.color == Color.black) {
				  w.right.color = Color.black;					// Case 3
				  w.color = Color.red;
				  leftRotate(w);
				  w = x.parent.left;
			  } else {
				  w.color = x.parent.color;				// Case 4
				  x.parent.color = Color.black;
				  w.left.color = Color.black;
				  rightRotate(x.parent);
				  break;
			  }
		   }
	   }
	   
	   x.color = Color.black;
	
   }

   /**
    * Finds the successor of to_success if such exists. Used by <code>delete()</code>.
    * @param to_success The node for which the successor is needed.
    * @return The RBNode of the next value after to_success.value or nil.
    */
   private RBNode successor(RBNode to_success) {
  	   if (to_success.right != nil) {
		   return min(to_success.right);
	   }
	   RBNode y = to_success.parent;
	   while ((y!= nil) && (to_success == y.right))
	   {
		   to_success = y;
		   y = y.parent;
	   }
	   return y;
   }
   

   /**
    * An overload of min for internal use. Finds the minimum of a subtree.  
    * Used by the public <code>min</code> and by <code>successor</code>.<br>
    * <u>Complexity:</u> Travels the height of the tree, at O(h) = O(logn)
    * @param subtree_root The root of the subtree whose minimum will be fetched
    * @return The minimum value of the subtree, or nil if the subtree is nil.
    */
   private RBNode min(RBNode subtree_root)
   {
	   if (subtree_root == nil) {
		   return nil;
	   }
	   
	   RBNode i = subtree_root;
	   
	   while (i.left != nil) {
		   i = i.left;
	   }
	   
	   return i;
   }
   
 
   	
   	/**
   	 * isComplete_helper(RBNode node)
   	 * 
   	 * This recursive function is used to implement isComplete.
   	 * 
   	 * It uses the following logic: a tree is complete if both its child-trees
   	 * are complete, and in addition the depth of the tree is uniform.
   	 * 
   	 * <u>Complexity:</u> This function will iterate on every node in the tree
	 * and perform O(1) operations. Total: O(n).
   	 * @param node The (sub)tree to be checked for completeness
   	 * @return -1 if <code>node</code> is not a complete tree, otherwise its height.
   	 */
   private static int isComplete_helper(RBNode node) {
	   if (node.right == nil && node.left == nil) {
		   return 1;
	   }
	   
	   if (node.right == nil && node.left != nil) {
		   return -1;
	   }
	   
	   if (node.left == nil && node.right != nil) {
		   return -1;
	   }
	   
	   // here we know node.right and node.left are not null
	   int result1 = isComplete_helper(node.right);
	   int result2 = isComplete_helper(node.left);
	   
	   if ((result1 != result2) ||
			   result1 == -1 || result2 == -1) {
		   return -1;
	   } else {
		   return result1 + 1;
	   }
   }
   
  	/**
  	 * Traverses the tree in-order started with the given node, filling the array.
  	 * Used by <code>toIntArray()</code>.<br>
  	 * <u>Complexity:</u> This is a recursive method, so we will use the master theorem 
  	 * to check its complexity:<br>
  	 * T(n) = 2T(n/2) + O(1) ==> n^(log_2(2) = n = O(f) ==> T(n) = \Theta(n).
  	 * @param node The node from which the begin the traversal.
  	 * @param elementsArray The array to fill with the subtree's elements
  	 * @param idx The offset at which to begin filling the array - the first empty slot.
  	 * @return A past-the-end point on the array for where it has been filled up to so far
  	 * for the usage of the next phase of the recursion.
  	 */
	private int inOrder(RBNode node, int[] elementsArray, int idx) {
		if (node.left != nil) {
			idx = inOrder(node.left, elementsArray, idx);
		}
		elementsArray[idx] = node.value;
		idx++;
		
		if (node.right != nil) {
			idx = inOrder(node.right, elementsArray, idx);
		}
		
		return idx;
		
	}

/**
   * A node in the RBTree. Contains integer key (value), pointers to children 
   * and parent, and color defined by Color enum. 
   */
	public static class RBNode {
		/**
		 * The integer key of the node.
		 */
		public int value;
		public RBNode right, left, parent;
		public Color color;
		
		/**
		 * A constructor for quickly creating a ready-to-insert node.
		 * @param value The new node's key
		 * @param parent The new node's intended parent node
		 * @param color The new node's color
		 */
		public RBNode(int value, RBNode parent, Color color) {
			this.value = value;
			this.parent = parent;
			this.color = color;
			this.left = nil;
			this.right = nil;
		}
		
		@Override
		public String toString() {
			return "RBNode value: " + value;
		}
	}
  
	/**
	 * colorStr(RBNode node)
	 * 
	 * This function takes a node and returns "r" if it is red and "b" if it is black.
	 * 
	 */
	private static String colorStr(RBNode node) {
		if (node == nil)
			return "";
		
		if (node.color == Color.black)
			return "b";
		
		return "r";
	}
	
	/**
	 * toStringHelper(RBNode node)
	 * 
	 * This function recursively implements a tree toString. This is the output format:
	 * 
	 * (left_subtree value right_subtree)
	 * 
	 * and the root of the tree is marked with triangular brackets.
	 */
	private static String toStringHelper(RBNode node) {
		if (node == nil) {
			return "";
		}
		
		if (node.parent == nil) // root
			return "(" + toStringHelper(node.left) + " <" + colorStr(node) + node.value + "> " + toStringHelper(node.right) + ")";
		return "(" + toStringHelper(node.left) + " " + colorStr(node) + node.value + " " + toStringHelper(node.right) + ")";
	}
	
	
	@Override
	public String toString() {
		return toStringHelper(root);
	}
	
	/**
	 * A static constant nil used as a sentinel node to ease the 
	 * implementation of complex methods like delete.
	 */
	static RBNode nil = new RBNode(0, null, Color.black);
  /**
 * @author Noam Mor, Hila Peleg
 *
 */

}
  

